/**
 * @author TTDB
 * @create 2025/9/9
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        insertionSort(arr);
        System.out.println("选择排序结果: " + java.util.Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // 从第二个元素开始（第一个元素视为已排序）
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前要插入的元素
            int j = i - 1;

            // 将比key大的元素向后移动---对以及排序的部分操作
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 插入key到正确位置
            arr[j + 1] = key;
        }
    }
}
